package com.dy.栈;

import com.dy.栈.链栈.LinkStack;

import java.util.Stack;

/*
后缀表达式，又称逆波兰式，指的是不包含括号，运算符放在两个运算对象的后面
1.遇到操作数：直接输出（添加到后缀表达式中）
2.栈为空时，遇到运算符，直接入栈
3.遇到左括号：将其入栈
4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，括号不输出。
5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
6.最终将栈中的元素依次出栈，输出。


 */
public class 后缀表达式 {
    public static void main(String[] args) throws Exception {
        后缀表达式 solution = new 后缀表达式();
        //6*(5+(2+3)*8+3)
        System.out.println(solution.numberCalculate(solution.convert2Postfix("6*(5+(2+3)*8+3)")));
    }

    //计算逆波兰表达式
    public double numberCalculate(String postfix) {
        Stack<Double> st = new Stack<>();
        for (int i = 0; i < postfix.length(); i++) {
            char c = postfix.charAt(i);
            if (isOperator(c)) {
                double d2 = st.pop();
                double d1 = st.pop();
                double d3 = 0;
                if ('+' == c) {
                    d3 = d1 + d2;
                } else if ('-' == c) {
                    d3 = d1 - d2;
                } else if ('*' == c) {
                    d3 = d1 * d2;
                } else if ('/' == c) {
                    d3 = d1 / d2;
                }
                st.push(d3);
            } else st.push(Double.valueOf(String.valueOf(c)));
        }
        return st.peek();
    }

    //生成波兰表达式
    public String convert2Postfix(String expression) throws Exception {
        LinkStack stack = new LinkStack();
        StringBuilder sb = new StringBuilder("");

        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (c == ' ') continue;
                //左括号直接入栈
            else if (c == '(') stack.push(c);
                //右括号，出栈添加到输出中，直到遇到左括号
            else if (c == ')') {
                char tmp = (char) stack.pop();
                while (tmp != '(') {
                    sb.append(tmp);
                    tmp = (char) stack.pop();
                }

            }
            //符号，当栈顶优先级大于当前优先级，出栈并输出，然后入栈当前符号
            else if (isOperator(c)) {
                if (!stack.isEmpty()) {
                    Character top = (Character) stack.peek();

                    while (top != null && priority(top) >= priority(c)) {
                        sb.append(top);
                        stack.pop();
                        top = (Character) stack.peek();
                    }
                    stack.push(c);
                } else
                    stack.push(c);
            }
            //添加操作数
            else {
                sb.append(c);
            }

        }
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.toString();
    }


    public boolean isOperator(char c) {
        if (c == '*' || c == '/' || c == '%' || c == '^' || c == '+' || c == '-') {
            return true;
        } else {
            return false;
        }
    }

    public int priority(char c) {
        if (c == '^') return 3;
        else if (c == '*' || c == '/' || c == '%') return 2;
        else if (c == '+' || c == '-') return 1;
        else return 0;
    }
}
